package leetcode.D600.T560;

import java.util.HashMap;
import java.util.Map;

class Solution {
    // 一刷
    /*public int subarraySum(int[] nums, int k) {
        int[] sums = new int[nums.length+1];
        int sum = 0, result = 0;
        for(int i=0; i<nums.length; ++i) {
            sum += nums[i];
            sums[i+1] = sum;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<sums.length; ++i) {
            if(!map.containsKey(sums[i])) {
                map.put(sums[i], new ArrayList<>());
            }
            map.get(sums[i]).add(i);
        }
        for(int i=1; i<sums.length; ++i) {
            int target = sums[i] - k;
            if(!map.containsKey(target)) {
                continue;
            }
            List<Integer> temp = map.get(target);
            for (int j : temp) {
                if(j >= i) {
                    break;
                }
                result++;
            }
        }
        return result;
    }*/

    // 二刷
    /*public int subarraySum(int[] nums, int k) {
        int result = 0;
        int[] sum = new int[nums.length+1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for(int i=0; i<nums.length; ++i) {
            sum[i+1] = sum[i] + nums[i];
            result += map.getOrDefault(sum[i+1]-k, 0);
            map.put(sum[i+1], map.getOrDefault(sum[i+1], 0)+1);
        }
        return result;
    }*/

    // 三刷
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int res = 0;
        int[] sum = new int[nums.length+1];
        for (int i=0; i<nums.length; ++i) {
            sum[i+1] = sum[i] + nums[i];
            res += map.getOrDefault(sum[i+1]-k, 0);
            map.put(sum[i+1], map.getOrDefault(sum[i+1], 0) + 1);
        }
        return res;
    }
}